|
从本文开始咱们一起探索 Go map 里面的奥妙吧，看看它的内在是怎么构成的，又分别有什么值得留意的地方？
第一篇将探讨初始化和访问元素相关板块，咱们带着疑问去学习，例如：
初始化的时候会马上分配内存吗？底层数据是如何存储的？底层是如何使用 key 去寻找数据的？底层是用什么方式解决哈希冲突的？数据类型那么多，底层又是怎么处理的呢？
…
数据结构首先我们一起看看 Go map 的基础数据结构，先有一个大致的印象
hmaptype hmap struct {
count int
flags uint8
B uint8
noverflow uint16
hash0 uint32
buckets unsafe.Pointer
oldbuckets unsafe.Pointer
nevacuate uintptr
extra *mapextra
}
type mapextra struct {
overflow *[]*bmap
oldoverflow *[]*bmap
nextOverflow *bmap
}
count：map 的大小，也就是 len() 的值。代指 map 中的键值对个数flags：状态标识，主要是 goroutine 写入和扩容机制的相关状态控制。并发读写的判断条件之一就是该值B：桶，最大可容纳的元素数量，值为 负载因子（默认 6.5） * 2 ^ B，是 2 的指数noverflow：溢出桶的数量hash0：哈希因子buckets：保存当前桶数据的指针地址（指向一段连续的内存地址，主要存储键值对数据）oldbuckets，保存旧桶的指针地址nevacuate：迁移进度extra：原有 buckets 满载后，会发生扩容动作，在 Go 的机制中使用了增量扩容，如下为细项：
overflow 为 hmap.buckets （当前）溢出桶的指针地址oldoverflow 为 hmap.oldbuckets （旧）溢出桶的指针地址nextOverflow 为空闲溢出桶的指针地址
在这里我们要注意几点，如下：
如果 keys 和 values 都不包含指针并且允许内联的情况下。会将 bucket 标识为不包含指针，使用 extra 存储溢出桶就可以避免 GC 扫描整个 map，节省不必要的开销在前面有提到，Go 用了增量扩容。而 buckets 和 oldbuckets 也是与扩容相关的载体，一般情况下只使用 buckets，oldbuckets 是为空的。但如果正在扩容的话，oldbuckets 便不为空，buckets 的大小也会改变当 hint 大于 8 时，就会使用 *mapextra 做溢出桶。若小于 8，则存储在 buckets 桶中
bmap
bucketCntBits = 3
bucketCnt = 1 >= 1
}
oldb := (*bmap)(add(c, (hash&m)*uintptr(t.bucketsize)))
if !evacuated(oldb) {
b = oldb
}
}
top := tophash(hash)
for ; b != nil; b = b.overflow(t) {
for i := uintptr(0); i < bucketCnt; i++ {
if b.tophash[i] != top {
continue
}
k := add(unsafe.Pointer(b), dataOffset+i*uintptr(t.keysize))
if t.indirectkey {
k = *((*unsafe.Pointer)(k))
}
if alg.equal(key, k) {
v := add(unsafe.Pointer(b), dataOffset+bucketCnt*uintptr(t.keysize)+i*uintptr(t.valuesize))
if t.indirectvalue {
v = *((*unsafe.Pointer)(v))
}
return v
}
}
}
return unsafe.Pointer(&zeroVal[0])
}
判断 map 是否为 nil，长度是否为 0。若是则返回零值判断当前是否并发读写 map，若是则抛出异常根据 key 的不同类型调用不同的 hash 方法计算得出 hash 值确定 key 在哪一个 bucket 中，并得到其位置判断是否正在发生扩容（h.oldbuckets 是否为 nil），若正在扩容，则到老的 buckets 中查找（因为 buckets 中可能还没有值，搬迁未完成），若该 bucket 已经搬迁完毕。则到 buckets 中继续查找计算 hash 的 tophash 值（高八位）根据计算出来的 tophash，依次循环对比 buckets 的 tophash 值（快速试错）如果 tophash 匹配成功，则计算 key 的所在位置，正式完整的对比两个 key 是否一致若查找成功并返回，若不存在，则返回零值
在上述步骤三中，提到了根据不同的类型计算出 hash 值，另外会计算出 hash 值的高八位和低八位。低八位会作为 bucket index，作用是用于找到 key 所在的 bucket。而高八位会存储在 bmap tophash 中
其主要作用是在上述步骤七中进行迭代快速定位。这样子可以提高性能，而不是一开始就直接用 key 进行一致性对比
图示
总结在本章节，我们介绍了 map 类型的以下知识点：
map 的基础数据结构初始化 map访问 map
从阅读源码中，得知 Go 本身对于一些不同大小、不同类型的属性，包括哈希方法都有编写特定方法去运行。总的来说，这块的设计隐含较多的思路，有不少点值得细细品尝 :)
注：本文基于 Go 1.11.5 最后编辑: kuteng 文档更新时间: 2020-12-27 14:34 作者：kuteng
|